#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstring>
#include "BalanceTree.h"

template<typename Tree> void balanceTreeSort(std::vector<int> & data)
{
    Tree tree;
    for(const int & x : data)
        tree.insert(x);
    data.clear();
    while(!tree.isEmpty())
    {
        data.push_back(tree.findMin());
        tree.remove(data.back());
    }
}

bool isIncreasing(const std::vector<int> & arr)
{
    for(int i = 0; i < arr.size() - 1; i++)
        if(arr[i] > arr[i+1]) return false;
    return true;
}

template<typename Tree> void testSort(const std::vector<int> & input)
{
    int _t = clock();
    std::cout << "Initializing..." << std::endl;
    std::vector<int> arr = input;
    std::cout << "Sorting..." << std::endl;
    balanceTreeSort<Tree>(arr);
    std::cout << "Finished. Time: " << (double) (clock() - _t) / CLOCKS_PER_SEC * 1000 << "ms" << std::endl;
    std::cout << "Result: " << (isIncreasing(arr) ? "Passed" : "Failed") << std::endl;
}

int main(int argc, char * argv[])
{
    int n;
    std::vector<int> input;
    srand(time(0));

    sscanf(argv[1], "%d", &n);
    if(argc == 3)
    {
        if(std::string(argv[2]) == "-i")
        {
            for(int i = 0; i < n; i++)
                input.push_back(i);
        }
        else
        {
            std::cout << "Unrecognized command " << argv[2] << std::endl;
            return 1;
        }
    }
    else
    {
        for(int i = 0; i < n; i++)
            input.push_back(rand());
    }

    std::cout << "---------------------------------test_AVL_sort-----------------------------------" << std::endl;
    testSort< AVL<int> >(input);
    std::cout << "--------------------------------test_Splay_sort----------------------------------" << std::endl;
    testSort< Splay<int> >(input);

    return 0;
}